{
 "cells": [
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-03-26T04:26:11.213533Z",
     "start_time": "2025-03-26T04:26:07.946359Z"
    }
   },
   "source": [
    "import pyclipper\n",
    "import matplotlib.pyplot as plt\n",
    "from shapely.geometry import Polygon\n",
    "import numpy as np\n",
    "import triangle as tr"
   ],
   "outputs": [],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "--------------------\n",
    "创建多边形进行测试\n",
    "\n",
    "\n"
   ],
   "id": "d4ec572d77b987b0"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:26:12.502384Z",
     "start_time": "2025-03-26T04:26:12.480384Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def plot_polygon(polygon, facecolor='blue', edgecolor='black'):\n",
    "    \"\"\"绘制多边形\"\"\"\n",
    "    plt.fill(*polygon.exterior.xy, facecolor=facecolor, edgecolor=edgecolor)\n",
    "    for interior in polygon.interiors:\n",
    "        plt.fill(*interior.xy, facecolor='white', edgecolor=edgecolor)"
   ],
   "id": "146616a97804d662",
   "outputs": [],
   "execution_count": 2
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:26:13.834939Z",
     "start_time": "2025-03-26T04:26:13.818938Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def convex_partition(polygon):\n",
    "    \"\"\"使用 PyClipper 进行凸分割\"\"\"\n",
    "    # 将多边形转换为 PyClipper 格式\n",
    "    pc = pyclipper.Pyclipper()\n",
    "    pc.AddPath(polygon.exterior.coords[:-1], pyclipper.PT_SUBJECT)\n",
    "    \n",
    "    # 执行凸分割\n",
    "    solution = pc.Execute(pyclipper.CT_UNION, pyclipper.PFT_NONZERO)\n",
    "    \n",
    "    # 转换为 Shapely 多边形\n",
    "    convex_parts = [Polygon(part) for part in solution]\n",
    "    return convex_parts"
   ],
   "id": "3d71cb2e9bfb26f9",
   "outputs": [],
   "execution_count": 3
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:27:00.237815Z",
     "start_time": "2025-03-26T04:27:00.218817Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def polygon_to_triangles(polygon):\n",
    "    \"\"\"将多边形分割为三角形（最简单的凸多边形）\"\"\"\n",
    "    # 提取顶点坐标\n",
    "    vertices = np.array(polygon.exterior.coords)\n",
    "    \n",
    "    # 创建三角形数据结构\n",
    "    A = {'vertices': vertices}\n",
    "    \n",
    "    # 添加孔洞（如果有）\n",
    "    if len(polygon.interiors) > 0:\n",
    "        holes = []\n",
    "        for interior in polygon.interiors:\n",
    "            holes.append(list(interior.coords)[0])  # 取每个孔的一个点\n",
    "        A['holes'] = np.array(holes)\n",
    "    \n",
    "    # 进行三角剖分\n",
    "    B = tr.triangulate(A, 'p')\n",
    "    \n",
    "    # 创建三角形多边形列表\n",
    "    triangles = []\n",
    "    for triangle in B['triangles']:\n",
    "        tri_vertices = B['vertices'][triangle]\n",
    "        triangles.append(Polygon(tri_vertices))\n",
    "    \n",
    "    return triangles"
   ],
   "id": "ec85037ff444130",
   "outputs": [],
   "execution_count": 11
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:28:27.737692Z",
     "start_time": "2025-03-26T04:28:27.368692Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 创建一个凹多边形（L形）\n",
    "polygon = Polygon([\n",
    "    (0, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)\n",
    "])\n",
    "\n",
    "# 使用相同的多边形\n",
    "convex_parts = convex_partition(polygon)\n",
    "\n",
    "# 绘制结果\n",
    "plt.figure(figsize=(10, 5))\n",
    "plt.subplot(1, 2, 1)\n",
    "plot_polygon(polygon)\n",
    "plt.title('Original Polygon')\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "for i, part in enumerate(convex_parts):\n",
    "    plot_polygon(part)\n",
    "plt.title('Convex Decomposition')\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ],
   "id": "11c353c120ebb831",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Figure size 1000x500 with 2 Axes>"
      ],
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA94AAAHqCAYAAADyGZa5AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAASfxJREFUeJzt3Xtc1GXe//H3KDCjJRQeABPQvBVEd13AA2hqZmJY3tWWWlukZVuWlcp2V9Ra0t5Flu16yDK7VdZK0iIPlZl45yGT3ES0uzJ/tatiCqu4yXhIFL1+fxizjhxkgK+Mw+v5eFx/fK+5vt+5rhm+fOY9R5sxxggAAAAAAFiiSUNPAAAAAAAAX0bwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGPPDFF19o+PDhCgsLU0BAgEJDQ3XrrbcqNzfXo+NMnjxZNputVnNYu3atbDab1q5dW6v9a+rqq6/W1VdfXaNxNpvN1Zo1a6bu3btr2rRpOn36tEfXuWvXLtlsNmVmZtZu0gAAr/XVV1/p7rvvVocOHeRwOHTppZcqLi5OL774ov71r3819PQuiPI6V978/f3VsmVL9ezZUxMnTtQ333zT0FO86NlsNk2ePNm1/e2332ry5MnatWtXhbGjR49W+/btL9jc0LgRvIEamjlzpvr27asff/xRL774olavXq2pU6dq7969uuqqq/TKK6/U+Fj33nuvx2G9XFxcnHJzcxUXF1er/a1w5ZVXKjc3V7m5uVq0aJGuuOIKTZw4UWlpaQ09NQCAF3jjjTcUHx+vL7/8Uv/1X/+llStXasmSJRo+fLhmz56tMWPGNPQUL6iHH35Yubm5Wrdund58803ddNNNWr58ubp3766XXnqpoad3UcvNzdW9997r2v7222+Vnp5eafCeNGmSlixZcgFnh8bMZowxDT0JwNt9/vnn6t+/v4YOHaolS5bIz8/PdVlZWZluvvlmrVixQuvXr1ffvn2rPM6xY8fUvHnzCzHlOit/tft8r6xfffXVKi4u1tdff+3qO3nypKKjo1VUVKRDhw7J39+/Rte5a9cudejQQfPnz9fo0aNrOXMAgDfJzc1Vv379NHjwYC1dulR2u93t8hMnTmjlypX6z//8zwaa4YVTXudeeuklPfroo26X/fzzz/rtb3+rlStXasWKFUpOTm6gWfqW9957T8OHD9eaNWtq9E4+wCq84g3UQEZGhmw2m1577TW30C1Jfn5+evXVV2Wz2fTCCy+4+svfTr5lyxbdeuutuvzyy9WxY0e3y85WWlqqP/zhDwoNDVXz5s3Vv39/5eXlqX379m4htLK3mo8ePVqXXnqpfvjhBw0dOlSXXnqpwsPD9Yc//EGlpaVu15Oenq7evXsrODhYgYGBiouL09y5c1Wfz8H5+/srPj5ex44d04EDByRJX3/9tW688UZdfvnlcjgc+s1vfqO//vWv1R7ns88+k81mU1ZWVoXLFixYIJvNpi+//NLV98Ybb6hz586y2+2KiYnRwoULK30b2b/+9S89+OCDuuKKKxQQEKArr7xSTz31VIXbymaz6aGHHtKbb76pLl26qHnz5urevbs+/PDDWt4yAND4PP/887LZbJozZ06F0C1JAQEBbqH79OnTevHFFxUdHS273a42bdrorrvu0o8//ui239VXX61u3brpyy+/VL9+/dS8eXNdeeWVeuGFF1wfdTpw4IACAgI0adKkCtf73XffyWazacaMGa6+oqIi3X///WrXrp0CAgLUoUMHpaenq6ysTJJkjNHQoUPVsmVLFRQUuPY7duyYunbtqi5duujo0aO1up2aNWumuXPnyt/fv8Kr3uebV7nS0lI9++yz6tKlixwOh1q2bKmBAwdq48aNrjHHjx9XWlqaOnTooICAAF1xxRUaN26cDh065Has9u3b64YbbtCHH36o2NhYNWvWTF26dHHVwMzMTHXp0kWXXHKJevXqpc2bN7vtX/7Y5JtvvtGgQYN0ySWXqHXr1nrooYd07Ngxt7E1ndOnn36qq6++Wi1btlSzZs0UERGhW265xe14Z7/VPDMzU8OHD5ckDRw40PUW//KPtFX2GMHT22flypWKi4tTs2bNFB0drXnz5gmolAFQrbKyMtO8eXPTu3fvasf16tXLNG/e3JSVlRljjHnmmWeMJBMZGWkef/xxk5OTY5YuXep22dluv/1206RJE/PEE0+YVatWmWnTppnw8HATFBRkRo0a5Rq3Zs0aI8msWbPG1Tdq1CgTEBBgunTpYqZOnWpWr15tnn76aWOz2Ux6errb9YwePdrMnTvX5OTkmJycHPOnP/3JNGvWrMK4AQMGmAEDBpz39hkwYIDp2rVrhf64uDjj5+dnjh07Zr777jvTokUL07FjR7NgwQLz0Ucfmdtvv91IMlOmTHHts3PnTiPJzJ8/39UXGxtr+vbtW+H4PXv2ND179nRtv/7660aSueWWW8yHH35o3n77bdO5c2cTGRlpIiMjXeN+/vln8+tf/9pccsklZurUqWbVqlVm0qRJxs/PzwwdOtTtOiSZ9u3bm169epnFixebFStWmKuvvtr4+fmZv//97+e9bQCgsatpDT3bfffdZySZhx56yKxcudLMnj3btG7d2oSHh5sDBw64xg0YMMC0bNnSdOrUycyePdvk5OSYBx980Egyf/3rX13jbr75ZhMeHm5OnTrldj2PPfaYCQgIMMXFxcYYYwoLC014eLiJjIw0r7/+ulm9erX505/+ZOx2uxk9erRrv+LiYtOuXTvTu3dvc+LECWPMmTrcrFkz89VXX1W7tvI699JLL1U5JiEhwdjtdnPy5EmP5nXy5EkzcOBA4+fnZx599FGzYsUKs3z5cvPkk0+arKwsY4wxp0+fNkOGDDF+fn5m0qRJZtWqVWbq1KnmkksuMbGxseb48eOu40VGRpp27dqZbt26maysLLNixQrTu3dv4+/vb55++mnTt29f8/7775slS5aYzp07m5CQEHPs2DHX/uWPTSIiIsxzzz1nVq1aZSZPnmz8/PzMDTfc4BpX0znt3LnTOBwOM3jwYLN06VKzdu1a8/bbb5uUlBTz008/uY4nyTzzzDPGGGP2799vnn/+eSPJzJo1y+Tm5prc3Fyzf/9+1xzPfoxQm9snJibGLFiwwHzyySdm+PDhRpJZt25dtX8HaJwI3sB5FBUVGUnmtttuq3bcyJEjjSTzz3/+0xjz73D99NNPVxh7bvD+5ptvjCTz+OOPu43LysoykmoUvCWZxYsXu+0/dOhQExUVVeWcT506ZU6ePGmeffZZ07JlS3P69GnXZZ4G75MnT5qTJ0+affv2mSeeeMJIMsOHDzfGGHPbbbcZu91uCgoK3PZNTk42zZs3N4cOHTLGVB6858+fbySZ/Px8V9/f/vY3twdWp06dMqGhoRUe2O3evdv4+/u7FdXZs2dXeltNmTLFSDKrVq1y9UkyISEhxul0uvqKiopMkyZNTEZGxnlvGwBo7GpaQ8tt377dSDIPPvigW/+mTZuMJPPkk0+6+gYMGGAkmU2bNrmNjYmJMUOGDHFtL1++vML/97KyMtO2bVtzyy23uPruv/9+c+mll5rdu3e7HW/q1KlGkvnmm29cfRs2bDB+fn5mwoQJZt68eUaS+Z//+Z/zrq8mwfvcxxM1ndeCBQuMJPPGG29UeeyVK1caSebFF19061+0aJGRZObMmePqi4yMNM2aNTM//vijq2/r1q1GkgkLCzNHjx519S9dutRIMsuXL3f1lT82mT59utt1Pffcc0aS2bBhg0dzeu+994wks3Xr1irXZ4x78DbGmHfffbfC46az53j2YwRPbx+Hw+F2v/z8888mODjY3H///dXOEY0TbzUH6on55a3a576F/JZbbjnvvuvWrZMkjRgxwq3/1ltvrfDW9qrYbDYNGzbMre/Xv/61du/e7db36aef6tprr1VQUJCaNm0qf39/Pf300zp48KD2799fo+s61zfffCN/f3/5+/urbdu2evnll3XHHXfojTfecF3noEGDFB4e7rbf6NGjdezYsWq/aO72229XmzZtNGvWLFffzJkz1bp1a40cOVKStGPHDhUVFVW4/SIiIip85v7TTz/VJZdcoltvvbXCXCTpf//3f936Bw4cqBYtWri2Q0JC1KZNmwq3KwCg7tasWSNJFb7no1evXurSpUuF/9GhoaHq1auXW9+5tS85OVmhoaGaP3++q++TTz7Rvn37dM8997j6PvzwQw0cOFBt27ZVWVmZq5V/1rq8VktS37599dxzz2natGl64IEHdOedd9bbF8SZcz76VdN5ffzxx3I4HG5rOtenn34qqeLtO3z4cF1yySUVbt/f/OY3uuKKK1zbXbp0kXTmbf5nf2dNeX9ltfGOO+5w2/7d734n6d/3dU3n9Jvf/EYBAQG677779Ne//lX/+Mc/qlxnbdXm9omIiHBtOxwOde7cmccIqBTBGziPVq1aqXnz5tq5c2e143bt2qXmzZsrODjYrT8sLOy813Hw4EFJZ0Ld2fz8/NSyZcsazbN58+ZyOBxufXa7XcePH3dt/+1vf1NSUpKkM5+H/vzzz/Xll1/qqaeeknTmi11qo2PHjvryyy+1efNmff311zp06JDeeustBQUFudZX2e3Qtm1b1+VVsdvtuv/++7Vw4UIdOnRIBw4c0OLFi3Xvvfe6PitY1e1XWd/BgwcVGhpa4QmSNm3ayM/Pr8JcKrv97XZ7rW8rAGhMalpDy5X/D66qZtTmf7Sfn59SUlK0ZMkS1+d0MzMzFRYWpiFDhrjG/fOf/9QHH3zgeiK5vHXt2lWSVFxc7HY9d9xxhwICAlRaWqr/+q//qtH6amL37t2y2+2uxxM1ndeBAwfUtm1bNWlS9cP7gwcPys/PT61bt3brt9lsCg0NrXD7nvuYJiAgoNr+sx9zSJU/jgkNDXXNxZM5dezYUatXr1abNm00btw4dezYUR07dtT06dOrXK+nPL19eIwAT9TspTSgEWvatKkGDhyolStX6scff1S7du0qjPnxxx+Vl5en5ORkNW3a1O2ymvxed/k/7n/+859uzyyXlZVVG0o99c4778jf318ffvihW0hfunRpnY7rcDjUo0ePKi9v2bKlCgsLK/Tv27dP0pkHZtV54IEH9MILL2jevHk6fvy4ysrKNHbsWLfjS2duv3MVFRVVmMumTZtkjHG7b/bv36+ysrLzzgUAUHNNmzbVoEGD9PHHH1dZQ89W/v+8sLCwwth9+/bV+n/03XffrZdeeknvvPOORo4cqeXLl2vChAluNbtVq1b69a9/reeee67SY5Q/WSxJp06d0h133KHLL79cdrtdY8aM0eeff+4KoLW1d+9e5eXlacCAAa53vNV0Xq1bt9aGDRt0+vTpKsN3y5YtVVZWpgMHDriFS2OMioqK1LNnzzrN/1zlj2PODqjldbm8z5M59evXT/369dOpU6e0efNmzZw5UxMmTFBISIhuu+22Os/3Qt8+aFx4xRuogbS0NBlj9OCDD+rUqVNul506dUoPPPCAjDG1/t3q/v37S5IWLVrk1v/ee+9V+MbSurDZbPLz83N7oPHzzz/rzTffrLfrqMygQYP06aefuoJ2uQULFqh58+ZKSEiodv+wsDANHz5cr776qmbPnq1hw4a5vbUrKipKoaGhWrx4sdt+BQUFbt/kWj6XI0eOVHiyYcGCBa7LAQD1p7yG/v73v9eJEycqXH7y5El98MEHkqRrrrlGkvTWW2+5jfnyyy+1ffv2Wv+P7tKli3r37q358+dr4cKFKi0t1d133+025oYbbtDXX3+tjh07qkePHhXa2cH7mWee0Weffaa3335bixYt0rZt2+r8qvfPP/+se++9V2VlZXrsscc8nldycrKOHz/u+sbuypTffufevtnZ2Tp69KglNfDtt9922164cKGkf/9saW3m1LRpU/Xu3dv1MbQtW7ZUef3l746ryavQDXH7oPHgFW+gBvr27atp06ZpwoQJuuqqq/TQQw8pIiJCBQUFmjVrljZt2qRp06apT58+tTp+165ddfvtt+vll19W06ZNdc011+ibb77Ryy+/rKCgoGrfNuaJ66+/Xn/+85/1u9/9Tvfdd58OHjyoqVOnVvrzLvXpmWeecX1G7emnn1ZwcLDefvttffTRR3rxxRddb0mvzvjx49W7d29JcvucniQ1adJE6enpuv/++3Xrrbfqnnvu0aFDh5Senq6wsDC32++uu+7SrFmzNGrUKO3atUu/+tWvtGHDBj3//PMaOnSorr322vpdPAA0comJiXrttdf04IMPKj4+Xg888IC6du2qkydPKj8/X3PmzFG3bt00bNgwRUVF6b777tPMmTPVpEkTJScna9euXZo0aZLCw8M1ceLEWs/jnnvu0f333699+/apT58+ioqKcrv82WefVU5Ojvr06aNHHnlEUVFROn78uHbt2qUVK1Zo9uzZateunXJycpSRkaFJkya5glhGRoYeffRRXX311br55pvPO5eCggJ98cUXOn36tEpKSpSfn6958+Zp9+7devnll10fC/NkXrfffrvmz5+vsWPHaseOHRo4cKBOnz6tTZs2qUuXLrrttts0ePBgDRkyRI8//ricTqf69u2rr776Ss8884xiY2OVkpJS69u3MgEBAXr55Zd15MgR9ezZUxs3btR///d/Kzk5WVdddZUk1XhOs2fP1qeffqrrr79eEREROn78uOunu6qr3d26dZMkzZkzRy1atJDD4VCHDh0qfZv4hb590Mg02Ne6AReh3Nxcc+utt5qQkBDj5+dn2rRpY37729+ajRs3Vhhb/s3lZ//0ybmXne348eMmNTXVtGnTxjgcDpOQkGByc3NNUFCQmThxomtcVd9qfskll9ToeubNm2eioqKM3W43V155pcnIyDBz5841kszOnTtd4+r6c2Ln+r//+z8zbNgwExQUZAICAkz37t3dvr3cmMq/1fxs7du3N126dKnyOubMmWP+4z/+wwQEBJjOnTubefPmmRtvvNHExsa6jTt48KAZO3asCQsLM35+fiYyMtKkpaW5/UyIMWe+GXXcuHEVricyMtLtm+YBAOe3detWM2rUKBMREWECAgJcP9H09NNPu37eyZgzv1QxZcoU07lzZ+Pv729atWpl7rzzTrNnzx6341VVf879pupyJSUlplmzZtV+8/eBAwfMI488Yjp06GD8/f1NcHCwiY+PN0899ZQ5cuSI2bdvn2nTpo255ppr3H6e7PTp02bYsGHmsssuc6ul5yqvc+WtadOm5vLLLzfx8fFmwoQJbt+c7sm8yv3888/m6aefNp06dTIBAQGmZcuW5pprrnF7nPLzzz+bxx9/3ERGRhp/f38TFhZmHnjgAbef5DLmTK27/vrrK8ylstpY2be1lz82+eqrr8zVV19tmjVrZoKDg80DDzzgNueazik3N9fcfPPNJjIy0tjtdtOyZUszYMAAt29SL5/f2d9qbowx06ZNMx06dDBNmzZ1e5xR2d9KXW+fmj5+QuNjM+acr04E4DU2btyovn376u2333Z9C2hj9dVXX6l79+6aNWuWHnzwwRrtc+jQIXXu3Fk33XST5syZY/EMAQBAudGjR+u9997TkSNHGnoqgFfgreaAl8jJyVFubq7i4+PVrFkzbdu2TS+88II6deqk3/72tw09vQbz97//Xbt379aTTz6psLCwCj/xUa6oqEjPPfecBg4cqJYtW2r37t36y1/+osOHD2v8+PEXdtIAAADAWQjegJcIDAzUqlWrNG3aNB0+fFitWrVScnKyMjIyKvxMWGPypz/9SW+++aa6dOmid9991+13Q89mt9u1a9cuPfjgg/rXv/7l+tK22bNnu35yBQAAAGgIvNUcAAAAAAAL8XNiAAAAAABYiOANAAAAAICFCN4AAAAAAFjIZ75c7fTp09q3b59atGghm83W0NMBAKDWjDE6fPiw2rZtqyZNfOs5cuo1AMBXeFKvfSZ479u3T+Hh4Q09DQAA6s2ePXvUrl27hp5GvaJeAwB8TU3qtc8E7xYtWkg6s+jAwMAGng0AALXndDoVHh7uqm2+hHoNAPAVntRrnwne5W9XCwwMpJADAHyCL74Vm3oNAPA1NanXvvXBMQAAAAAAvAzBGwAAAAAACxG8AQAAAACwEMEbAAAAAAALEbwBAAAAALAQwRsAAAAAAAsRvAEAAAAAsBDBGwAAAAAACxG8AQAAAACwEMEbAAAAAAALEbwBAAAAALAQwRsAAAAAAAt5FLwzMjLUs2dPtWjRQm3atNFNN92kHTt2nHe/devWKT4+Xg6HQ1deeaVmz55dYUx2drZiYmJkt9sVExOjJUuWeDI1AABwFmo2AADew6PgvW7dOo0bN05ffPGFcnJyVFZWpqSkJB09erTKfXbu3KmhQ4eqX79+ys/P15NPPqlHHnlE2dnZrjG5ubkaOXKkUlJStG3bNqWkpGjEiBHatGlT7VcGAEAjRs0GAMB72IwxprY7HzhwQG3atNG6devUv3//Ssc8/vjjWr58ubZv3+7qGzt2rLZt26bc3FxJ0siRI+V0OvXxxx+7xlx33XW6/PLLlZWVVaO5OJ1OBQUFqaSkRIGBgbVdEgAADc6KmuYtNZt6DQDwFZ7UtDp9xrukpESSFBwcXOWY3NxcJSUlufUNGTJEmzdv1smTJ6sds3HjxrpMDwAA/IKaDQBAw/Gr7Y7GGKWmpuqqq65St27dqhxXVFSkkJAQt76QkBCVlZWpuLhYYWFhVY4pKiqq8rilpaUqLS11bTudzlqupGoFBQUqLi6u9+MCF7NWrVopIiKioacBwAMNWbOp10DDoWYD3qPWwfuhhx7SV199pQ0bNpx3rM1mc9suf3f72f2VjTm372wZGRlKT0/3ZMoeKSgoUFRUFx0/fsyy6wAuRg5Hc+3YsZ1CDlxEGrJmU6+BhkPNBrxHrYL3ww8/rOXLl2v9+vVq165dtWNDQ0MrPAu+f/9++fn5qWXLltWOOfcZ9bOlpaUpNTXVte10OhUeHu7pUqpUXFz8SxF/S1KXejsucHHbruPH71RxcTFFHLhINHTNpl4DDYWaDXgTj4K3MUYPP/ywlixZorVr16pDhw7n3ScxMVEffPCBW9+qVavUo0cP+fv7u8bk5ORo4sSJbmP69OlT5XHtdrvsdrsn06+lLpLiLsD1AABQf7ylZlOvAQDw8MvVxo0bp7feeksLFy5UixYtVFRUpKKiIv3888+uMWlpabrrrrtc22PHjtXu3buVmpqq7du3a968eZo7d64effRR15jx48dr1apVmjJlir777jtNmTJFq1ev1oQJE+q+QgAAGiFqNgAAXsR4QFKlbf78+a4xo0aNMgMGDHDbb+3atSY2NtYEBASY9u3bm9dee63Csd99910TFRVl/P39TXR0tMnOzvZkaqakpMRIMiUlJR7tV5W8vLxf1pdnJEOj0WTMmfNBJi8vr17OMwCVq4+a5q01m3pNo12oRs0GrOZJTfP4rebnk5mZWaFvwIAB2rJlS7X73Xrrrbr11ls9mQ4AAKgCNRsAAO9Rp9/xBgAAAAAA1SN4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIY+D9/r16zVs2DC1bdtWNptNS5curXb86NGjZbPZKrSuXbu6xmRmZlY65vjx4x4vCAAAUK8BAPAmHgfvo0ePqnv37nrllVdqNH769OkqLCx0tT179ig4OFjDhw93GxcYGOg2rrCwUA6Hw9PpAQAAUa8BAPAmfp7ukJycrOTk5BqPDwoKUlBQkGt76dKl+umnn3T33Xe7jbPZbAoNDfV0OgAAoBLUawAAvMcF/4z33Llzde211yoyMtKt/8iRI4qMjFS7du10ww03KD8/v9rjlJaWyul0ujUAAFA/qNcAANSfCxq8CwsL9fHHH+vee+9164+OjlZmZqaWL1+urKwsORwO9e3bV99//32Vx8rIyHA9Ox8UFKTw8HCrpw8AQKNAvQYAoH5d0OCdmZmpyy67TDfddJNbf0JCgu688051795d/fr10+LFi9W5c2fNnDmzymOlpaWppKTE1fbs2WPx7AEAaByo1wAA1C+PP+NdW8YYzZs3TykpKQoICKh2bJMmTdSzZ89qn0G32+2y2+31PU0AABo16jUAAPXvgr3ivW7dOv3www8aM2bMeccaY7R161aFhYVdgJkBAIBy1GsAAOqfx694HzlyRD/88INre+fOndq6dauCg4MVERGhtLQ07d27VwsWLHDbb+7cuerdu7e6detW4Zjp6elKSEhQp06d5HQ6NWPGDG3dulWzZs2qxZIAAAD1GgAA7+Fx8N68ebMGDhzo2k5NTZUkjRo1SpmZmSosLFRBQYHbPiUlJcrOztb06dMrPeahQ4d03333qaioSEFBQYqNjdX69evVq1cvT6cHAABEvQYAwJvYjDGmoSdRH5xOp4KCglRSUqLAwMA6H2/Lli2Kj4+XlCcprs7HA3zDFknxysvLU1wc5wVglfquad6Eeg1cKNRswGqe1LQL/jveAAAAAAA0JgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQh4H7/Xr12vYsGFq27atbDabli5dWu34tWvXymazVWjfffed27js7GzFxMTIbrcrJiZGS5Ys8XRqAADgF9RrAAC8h8fB++jRo+revbteeeUVj/bbsWOHCgsLXa1Tp06uy3JzczVy5EilpKRo27ZtSklJ0YgRI7Rp0yZPpwcAAES9BgDAm/h5ukNycrKSk5M9vqI2bdrosssuq/SyadOmafDgwUpLS5MkpaWlad26dZo2bZqysrI8vi4AABo76jUAAN7jgn3GOzY2VmFhYRo0aJDWrFnjdllubq6SkpLc+oYMGaKNGzdeqOkBAABRrwEAsILHr3h7KiwsTHPmzFF8fLxKS0v15ptvatCgQVq7dq369+8vSSoqKlJISIjbfiEhISoqKqryuKWlpSotLXVtO51OaxYAAEAjQL0GAMA6lgfvqKgoRUVFubYTExO1Z88eTZ061VXIJclms7ntZ4yp0He2jIwMpaen1/+EAQBohKjXAABYp0F+TiwhIUHff/+9azs0NLTCs+X79++v8Kz62dLS0lRSUuJqe/bssWy+AAA0RtRrAADqR4ME7/z8fIWFhbm2ExMTlZOT4zZm1apV6tOnT5XHsNvtCgwMdGsAAKD+UK8BAKgfHr/V/MiRI/rhhx9c2zt37tTWrVsVHBysiIgIpaWlae/evVqwYIGkM9+A2r59e3Xt2lUnTpzQW2+9pezsbGVnZ7uOMX78ePXv319TpkzRjTfeqGXLlmn16tXasGFDPSwRAIDGh3oNAID38Dh4b968WQMHDnRtp6amSpJGjRqlzMxMFRYWqqCgwHX5iRMn9Oijj2rv3r1q1qyZunbtqo8++khDhw51jenTp4/eeecd/fGPf9SkSZPUsWNHLVq0SL17967L2gAAaLSo1wAAeA+bMcY09CTqg9PpVFBQkEpKSurlbWxbtmxRfHy8pDxJcXU+HuAbtkiKV15enuLiOC8Aq9R3TfMm1GvgQqFmA1bzpKY1yGe8AQAAAABoLAjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhTwO3uvXr9ewYcPUtm1b2Ww2LV26tNrx77//vgYPHqzWrVsrMDBQiYmJ+uSTT9zGZGZmymazVWjHjx/3dHoAAEDUawAAvInHwfvo0aPq3r27XnnllRqNX79+vQYPHqwVK1YoLy9PAwcO1LBhw5Sfn+82LjAwUIWFhW7N4XB4Oj0AACDqNQAA3sTP0x2Sk5OVnJxc4/HTpk1z237++ee1bNkyffDBB4qNjXX122w2hYaGejodAABQCeo1AADe44J/xvv06dM6fPiwgoOD3fqPHDmiyMhItWvXTjfccEOFZ9gBAMCFQ70GAKD+XPDg/fLLL+vo0aMaMWKEqy86OlqZmZlavny5srKy5HA41LdvX33//fdVHqe0tFROp9OtAQCA+kG9BgCg/nj8VvO6yMrK0uTJk7Vs2TK1adPG1Z+QkKCEhATXdt++fRUXF6eZM2dqxowZlR4rIyND6enpls8ZAIDGhnoNAED9umCveC9atEhjxozR4sWLde2111Y7tkmTJurZs2e1z6CnpaWppKTE1fbs2VPfUwYAoNGhXgMAUP8uyCveWVlZuueee5SVlaXrr7/+vOONMdq6dat+9atfVTnGbrfLbrfX5zQBAGjUqNcAAFjD4+B95MgR/fDDD67tnTt3auvWrQoODlZERITS0tK0d+9eLViwQNKZIn7XXXdp+vTpSkhIUFFRkSSpWbNmCgoKkiSlp6crISFBnTp1ktPp1IwZM7R161bNmjWrPtYIAECjQ70GAMB7ePxW882bNys2Ntb10yKpqamKjY3V008/LUkqLCxUQUGBa/zrr7+usrIyjRs3TmFhYa42fvx415hDhw7pvvvuU5cuXZSUlKS9e/dq/fr16tWrV13XBwBAo0S9BgDAe9iMMaahJ1EfnE6ngoKCVFJSosDAwDofb8uWLYqPj5eUJymuzscDfMMWSfHKy8tTXBznBWCV+q5p3oR6DVwo1GzAap7UtAv+c2IAAAAAADQmBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACzkcfBev369hg0bprZt28pms2np0qXn3WfdunWKj4+Xw+HQlVdeqdmzZ1cYk52drZiYGNntdsXExGjJkiWeTg0AAPyCeg0AgPfwOHgfPXpU3bt31yuvvFKj8Tt37tTQoUPVr18/5efn68knn9Qjjzyi7Oxs15jc3FyNHDlSKSkp2rZtm1JSUjRixAht2rTJ0+kBAABRrwEA8CY2Y4yp9c42m5YsWaKbbrqpyjGPP/64li9fru3bt7v6xo4dq23btik3N1eSNHLkSDmdTn388ceuMdddd50uv/xyZWVl1WguTqdTQUFBKikpUWBgYO0WdJYtW7YoPj5eUp6kuDofD/ANWyTFKy8vT3FxnBeAVeq7plGvgcaImg1YzZOa5mf1ZHJzc5WUlOTWN2TIEM2dO1cnT56Uv7+/cnNzNXHixApjpk2bVuVxS0tLVVpa6tp2Op31Om8AVTv7gTmAM1q1aqWIiIiGnkatUa8B30TNBtw1VL22PHgXFRUpJCTErS8kJERlZWUqLi5WWFhYlWOKioqqPG5GRobS09MtmTOAqrRSkybNdeeddzb0RACv43A0144d2y/a8E29BnwNNRuoTEPVa8uDt3TmLW5nK393+9n9lY05t+9saWlpSk1NdW07nU6Fh4fXx3QBVClCp09vl1Tc0BMBvMx2HT9+p4qLiy/a4C1RrwHfQs0GKmq4em158A4NDa3wTPj+/fvl5+enli1bVjvm3GfVz2a322W32+t/wgDOI+KXBsCXUK8BX0TNBryF5b/jnZiYqJycHLe+VatWqUePHvL39692TJ8+fayeHgAAEPUaAAArefyK95EjR/TDDz+4tnfu3KmtW7cqODhYERERSktL0969e7VgwQJJZ74R9ZVXXlFqaqp+//vfKzc3V3PnznX79tPx48erf//+mjJlim688UYtW7ZMq1ev1oYNG+phiQAAND7UawAAvIjx0Jo1a4ykCm3UqFHGGGNGjRplBgwY4LbP2rVrTWxsrAkICDDt27c3r732WoXjvvvuuyYqKsr4+/ub6Ohok52d7dG8SkpKjCRTUlLi6ZIqlZeX98va8oxkaDQajUarpp2pGXl5efVSg+qjplGvaTQajUY7tzVcva7T73h7E34XFADQcOr393Lru6Z5E+o1AKDhNFy9tvwz3gAAAAAANGYEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEK1Ct6vvvqqOnToIIfDofj4eH322WdVjh09erRsNluF1rVrV9eYzMzMSsccP368NtMDAACiXgMA4C08Dt6LFi3ShAkT9NRTTyk/P1/9+vVTcnKyCgoKKh0/ffp0FRYWutqePXsUHBys4cOHu40LDAx0G1dYWCiHw1G7VQEA0MhRrwEA8B4eB+8///nPGjNmjO6991516dJF06ZNU3h4uF577bVKxwcFBSk0NNTVNm/erJ9++kl333232zibzeY2LjQ0tHYrAgAA1GsAALyIR8H7xIkTysvLU1JSklt/UlKSNm7cWKNjzJ07V9dee60iIyPd+o8cOaLIyEi1a9dON9xwg/Lz8z2ZGgAA+AX1GgAA7+LnyeDi4mKdOnVKISEhbv0hISEqKio67/6FhYX6+OOPtXDhQrf+6OhoZWZm6le/+pWcTqemT5+uvn37atu2berUqVOlxyotLVVpaalr2+l0erIUAAB8FvUaAADvUqsvV7PZbG7bxpgKfZXJzMzUZZddpptuusmtPyEhQXfeeae6d++ufv36afHixercubNmzpxZ5bEyMjIUFBTkauHh4bVZCgAAPot6DQCAd/AoeLdq1UpNmzat8Gz5/v37Kzyrfi5jjObNm6eUlBQFBARUP6kmTdSzZ099//33VY5JS0tTSUmJq+3Zs6fmCwEAwIdRrwEA8C4eBe+AgADFx8crJyfHrT8nJ0d9+vSpdt9169bphx9+0JgxY857PcYYbd26VWFhYVWOsdvtCgwMdGsAAIB6DQCAt/HoM96SlJqaqpSUFPXo0UOJiYmaM2eOCgoKNHbsWElnntneu3evFixY4Lbf3Llz1bt3b3Xr1q3CMdPT05WQkKBOnTrJ6XRqxowZ2rp1q2bNmlXLZQEA0LhRrwEA8B4eB++RI0fq4MGDevbZZ1VYWKhu3bppxYoVrm89LSwsrPAboSUlJcrOztb06dMrPeahQ4d03333qaioSEFBQYqNjdX69evVq1evWiwJAABQrwEA8B42Y4xp6EnUB6fTqaCgIJWUlNTL29i2bNmi+Ph4SXmS4up8PACAL9siKV55eXmKi6t7zajvmuZNqNcAgIbTcPW6Vt9qDgAAAAAAaobgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYiOANAAAAAICFCN4AAAAAAFiI4A0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhWoVvF999VV16NBBDodD8fHx+uyzz6ocu3btWtlstgrtu+++cxuXnZ2tmJgY2e12xcTEaMmSJbWZGgAA+AX1GgAA7+Bx8F60aJEmTJigp556Svn5+erXr5+Sk5NVUFBQ7X47duxQYWGhq3Xq1Ml1WW5urkaOHKmUlBRt27ZNKSkpGjFihDZt2uT5igAAAPUaAABvYjzUq1cvM3bsWLe+6Oho88QTT1Q6fs2aNUaS+emnn6o85ogRI8x1113n1jdkyBBz22231XheJSUlRpIpKSmp8T7VycvLM5KMlGckQ6PRaDRaNe1MzcjLy6uXGlQfNY16TaPRaDTaua3h6rVHr3ifOHFCeXl5SkpKcutPSkrSxo0bq903NjZWYWFhGjRokNasWeN2WW5uboVjDhkypNpjlpaWyul0ujUAAEC9BgDA23gUvIuLi3Xq1CmFhIS49YeEhKioqKjSfcLCwjRnzhxlZ2fr/fffV1RUlAYNGqT169e7xhQVFXl0TEnKyMhQUFCQq4WHh3uyFAAAfBb1GgAA7+JXm51sNpvbtjGmQl+5qKgoRUVFubYTExO1Z88eTZ06Vf3796/VMSUpLS1Nqamprm2n00kxBwDgLNRrAAC8g0eveLdq1UpNmzat8Mz2/v37KzwDXp2EhAR9//33ru3Q0FCPj2m32xUYGOjWAAAA9RoAAG/jUfAOCAhQfHy8cnJy3PpzcnLUp0+fGh8nPz9fYWFhru3ExMQKx1y1apVHxwQAAGdQrwEA8C4ev9U8NTVVKSkp6tGjhxITEzVnzhwVFBRo7Nixks68pWzv3r1asGCBJGnatGlq3769unbtqhMnTuitt95Sdna2srOzXcccP368+vfvrylTpujGG2/UsmXLtHr1am3YsKGelgkAQONCvQYAwHt4HLxHjhypgwcP6tlnn1VhYaG6deumFStWKDIyUpJUWFjo9huhJ06c0KOPPqq9e/eqWbNm6tq1qz766CMNHTrUNaZPnz5655139Mc//lGTJk1Sx44dtWjRIvXu3bselggAQONDvQYAwHvYjDGmoSdRH5xOp4KCglRSUlIvnx/bsmWL4uPjJeVJiqvz8QAAvmyLpHjl5eUpLq7uNaO+a5o3oV4DABpOw9Vrjz7jDQAAAAAAPEPwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALFSr4P3qq6+qQ4cOcjgcio+P12effVbl2Pfff1+DBw9W69atFRgYqMTERH3yySduYzIzM2Wz2Sq048eP12Z6AABA1GsAALyFx8F70aJFmjBhgp566inl5+erX79+Sk5OVkFBQaXj169fr8GDB2vFihXKy8vTwIEDNWzYMOXn57uNCwwMVGFhoVtzOBy1WxUAAI0c9RoAAC9iPNSrVy8zduxYt77o6GjzxBNP1PgYMTExJj093bU9f/58ExQU5OlU3JSUlBhJpqSkpE7HKZeXl2ckGSnPSIZGo9FotGramZqRl5dXLzWoPmoa9ZpGo9FotHNbw9Vrj17xPnHihPLy8pSUlOTWn5SUpI0bN9boGKdPn9bhw4cVHBzs1n/kyBFFRkaqXbt2uuGGGyo8ww4AAGqGeg0AgHfxKHgXFxfr1KlTCgkJcesPCQlRUVFRjY7x8ssv6+jRoxoxYoSrLzo6WpmZmVq+fLmysrLkcDjUt29fff/991Uep7S0VE6n060BAADqNQAA3savNjvZbDa3bWNMhb7KZGVlafLkyVq2bJnatGnj6k9ISFBCQoJru2/fvoqLi9PMmTM1Y8aMSo+VkZGh9PT02kwfAIBGgXoNAIB38OgV71atWqlp06YVni3fv39/hWfVz7Vo0SKNGTNGixcv1rXXXlv9pJo0Uc+ePat9Bj0tLU0lJSWutmfPnpovBAAAH0a9BgDAu3gUvAMCAhQfH6+cnBy3/pycHPXp06fK/bKysjR69GgtXLhQ119//XmvxxijrVu3KiwsrMoxdrtdgYGBbg0AAFCvAQDwNh6/1Tw1NVUpKSnq0aOHEhMTNWfOHBUUFGjs2LGSzjyzvXfvXi1YsEDSmSJ+1113afr06UpISHA9+96sWTMFBQVJktLT05WQkKBOnTrJ6XRqxowZ2rp1q2bNmlVf6wQAoFGhXgMA4D08Dt4jR47UwYMH9eyzz6qwsFDdunXTihUrFBkZKUkqLCx0+43Q119/XWVlZRo3bpzGjRvn6h81apQyMzMlSYcOHdJ9992noqIiBQUFKTY2VuvXr1evXr3quDwAABon6jUAAN7DZowxDT2J+uB0OhUUFKSSkpJ6eRvbli1bFB8fLylPUlydjwcA8GVbJMUrLy9PcXF1rxn1XdO8CfUaANBwGq5ee/QZbwAAAAAA4BmCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYCGCNwAAAAAAFiJ4AwAAAABgIYI3AAAAAAAWIngDAAAAAGAhgjcAAAAAABYieAMAAAAAYKFaBe9XX31VHTp0kMPhUHx8vD777LNqx69bt07x8fFyOBy68sorNXv27ApjsrOzFRMTI7vdrpiYGC1ZsqQ2UwMAAL+gXgMA4B08Dt6LFi3ShAkT9NRTTyk/P1/9+vVTcnKyCgoKKh2/c+dODR06VP369VN+fr6efPJJPfLII8rOznaNyc3N1ciRI5WSkqJt27YpJSVFI0aM0KZNm2q/MgAAGjHqNQAAXsR4qFevXmbs2LFufdHR0eaJJ56odPxjjz1moqOj3fruv/9+k5CQ4NoeMWKEue6669zGDBkyxNx22201nldJSYmRZEpKSmq8T3Xy8vKMJCPlGcnQaDQajVZNO1Mz8vLy6qUG1UdNo17TaDQajXZua7h67dEr3idOnFBeXp6SkpLc+pOSkrRx48ZK98nNza0wfsiQIdq8ebNOnjxZ7ZiqjgkAAKpGvQYAwLv4eTK4uLhYp06dUkhIiFt/SEiIioqKKt2nqKio0vFlZWUqLi5WWFhYlWOqOqYklZaWqrS01LXtdDo9WYoHtlt0XACA7/CuWkG9BgCgMg1XKzwK3uVsNpvbtjGmQt/5xp/b7+kxMzIylJ6eXuM5e6pVq1ZyOJrr+PE7LbsOAIDvcDiaq1WrVg09DTfUawAA3DVUvfYoeLdq1UpNmzat8Mz2/v37KzwDXi40NLTS8X5+fmrZsmW1Y6o6piSlpaUpNTXVte10OhUeHu7JcqoVERGhHTu2q7i4uN6OCQDwXa1atVJERERDT0MS9RoAgKo0VL32KHgHBAQoPj5eOTk5uvnmm139OTk5uvHGGyvdJzExUR988IFb36pVq9SjRw/5+/u7xuTk5GjixIluY/r06VPlXOx2u+x2uyfT91hERITXPIgCAKCmqNcAAHgXj99qnpqaqpSUFPXo0UOJiYmaM2eOCgoKNHbsWElnntneu3evFixYIEkaO3asXnnlFaWmpur3v/+9cnNzNXfuXGVlZbmOOX78ePXv319TpkzRjTfeqGXLlmn16tXasGFDPS0TAIDGhXoNAID38Dh4jxw5UgcPHtSzzz6rwsJCdevWTStWrFBkZKQkqbCw0O03Qjt06KAVK1Zo4sSJmjVrltq2basZM2bolltucY3p06eP3nnnHf3xj3/UpEmT1LFjRy1atEi9e/euhyUCAND4UK8BAPAeNlP+zSkXOafTqaCgIJWUlCgwMLChpwMAQK35ck3z5bUBABoXT2qaR7/jDQAAAAAAPEPwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEIEbwAAAAAALETwBgAAAADAQgRvAAAAAAAsRPAGAAAAAMBCBG8AAAAAACxE8AYAAAAAwEJ+DT2B+mKMkSQ5nc4GngkAAHVTXsvKa5svoV4DAHyFJ/XaZ4L34cOHJUnh4eENPBMAAOrH4cOHFRQU1NDTqFfUawCAr6lJvbYZH3k6/fTp09q3b59atGghm81W5+M5nU6Fh4drz549CgwMrIcZXni+sAbJN9bhC2uQWIc38YU1SKyjKsYYHT58WG3btlWTJr71qTDqdeV8YR2+sAaJdXgTX1iDxDq8SUPWa595xbtJkyZq165dvR83MDDwov3DKucLa5B8Yx2+sAaJdXgTX1iDxDoq42uvdJejXlfPF9bhC2uQWIc38YU1SKzDmzREvfatp9EBAAAAAPAyBG8AAAAAACxE8K6C3W7XM888I7vd3tBTqTVfWIPkG+vwhTVIrMOb+MIaJNaBuvOV294X1uELa5BYhzfxhTVIrMObNOQafObL1QAAAAAA8Ea84g0AAAAAgIUI3gAAAAAAWIjgDQAAAACAhQjeAAAAAABYqNEE71dffVUdOnSQw+FQfHy8Pvvss2rHr1u3TvHx8XI4HLryyis1e/bsCmOys7MVExMju92umJgYLVmyxKrpu3iyjvfff1+DBw9W69atFRgYqMTERH3yySduYzIzM2Wz2Sq048ePe8Ua1q5dW+n8vvvuO7dx3n5fjB49utJ1dO3a1TXmQt8X69ev17Bhw9S2bVvZbDYtXbr0vPt443nh6Tq88bzwdA3eel54ug5vPC8yMjLUs2dPtWjRQm3atNFNN92kHTt2nHc/bzw3LlbUa+/4v1SbdXjr/6aLvV5LvlGzfaFe12Yd3npeULMv/LnRKIL3okWLNGHCBD311FPKz89Xv379lJycrIKCgkrH79y5U0OHDlW/fv2Un5+vJ598Uo888oiys7NdY3JzczVy5EilpKRo27ZtSklJ0YgRI7Rp0yavWcf69es1ePBgrVixQnl5eRo4cKCGDRum/Px8t3GBgYEqLCx0aw6HwyvWUG7Hjh1u8+vUqZPrsovhvpg+fbrb/Pfs2aPg4GANHz7cbdyFvC+OHj2q7t2765VXXqnReG89LzxdhzeeF56uoZy3nReersMbz4t169Zp3Lhx+uKLL5STk6OysjIlJSXp6NGjVe7jrefGxYh67T3/l2qzjnLe9L/JF+q15Bs12xfqtUTN9qZz46Kr2aYR6NWrlxk7dqxbX3R0tHniiScqHf/YY4+Z6Ohot77777/fJCQkuLZHjBhhrrvuOrcxQ4YMMbfddls9zboiT9dRmZiYGJOenu7anj9/vgkKCqqvKZ6Xp2tYs2aNkWR++umnKo95Md4XS5YsMTabzezatcvVd6Hvi7NJMkuWLKl2jLeeF2eryToq09DnxdlqsgZvPS/OVpv7wtvOC2OM2b9/v5Fk1q1bV+WYi+HcuFhQr//NG/4v+ULN9rV6bYxv1GxfqNfGULO97dzw9prt8694nzhxQnl5eUpKSnLrT0pK0saNGyvdJzc3t8L4IUOGaPPmzTp58mS1Y6o6Zl3VZh3nOn36tA4fPqzg4GC3/iNHjigyMlLt2rXTDTfcUOGZxPpSlzXExsYqLCxMgwYN0po1a9wuuxjvi7lz5+raa69VZGSkW/+Fui9qwxvPi/rQ0OdFXXjTeVEfvPG8KCkpkaQKfx9n89Vz40KjXv+bN/xf8oWa3VjrteSd50ZdecN5URfecl7UF288N7y9Zvt88C4uLtapU6cUEhLi1h8SEqKioqJK9ykqKqp0fFlZmYqLi6sdU9Ux66o26zjXyy+/rKNHj2rEiBGuvujoaGVmZmr58uXKysqSw+FQ37599f3339fr/KXarSEsLExz5sxRdna23n//fUVFRWnQoEFav369a8zFdl8UFhbq448/1r333uvWfyHvi9rwxvOiPjT0eVEb3nhe1JU3nhfGGKWmpuqqq65St27dqhznq+fGhUa9/jdv+L/kCzW7sdZryTvPjbryhvOiNrztvKgP3nhuXAw1269Oe19EbDab27YxpkLf+caf2+/pMetDba8zKytLkydP1rJly9SmTRtXf0JCghISElzbffv2VVxcnGbOnKkZM2bU38TP4skaoqKiFBUV5dpOTEzUnj17NHXqVPXv379Wx6wvtb3OzMxMXXbZZbrpppvc+hvivvCUt54XteVN54UnvPm8qC1vPC8eeughffXVV9qwYcN5x/raudGQqNfe9X/JF2p2Y6zXkveeG7XhbeeFJ7z1vKgLbzw3Loaa7fOveLdq1UpNmzat8AzF/v37KzyTUS40NLTS8X5+fmrZsmW1Y6o6Zl3VZh3lFi1apDFjxmjx4sW69tprqx3bpEkT9ezZ05JnpuqyhrMlJCS4ze9iui+MMZo3b55SUlIUEBBQ7Vgr74va8Mbzoi685byoLw19XtSFN54XDz/8sJYvX641a9aoXbt21Y71tXOjoVCvvev/ki/U7MZaryXvPDdqy5vOi/pCza5fF0vN9vngHRAQoPj4eOXk5Lj15+TkqE+fPpXuk5iYWGH8qlWr1KNHD/n7+1c7pqpj1lVt1iGdeYZw9OjRWrhwoa6//vrzXo8xRlu3blVYWFid53yu2q7hXPn5+W7zu1juC+nMty/+8MMPGjNmzHmvx8r7oja88byoLW86L+pLQ58XdeFN54UxRg899JDef/99ffrpp+rQocN59/Glc6MhUa+96/+SL9TsxlqvJe88N2rD286L+kLNrh8XXc2u01ezXSTeeecd4+/vb+bOnWu+/fZbM2HCBHPJJZe4voXviSeeMCkpKa7x//jHP0zz5s3NxIkTzbfffmvmzp1r/P39zXvvveca8/nnn5umTZuaF154wWzfvt288MILxs/Pz3zxxRdes46FCxcaPz8/M2vWLFNYWOhqhw4dco2ZPHmyWblypfn73/9u8vPzzd133238/PzMpk2bvGINf/nLX8ySJUvM//t//898/fXX5oknnjCSTHZ2tmvMxXBflLvzzjtN7969Kz3mhb4vDh8+bPLz801+fr6RZP785z+b/Px8s3v37krX4K3nhafr8MbzwtM1eOt54ek6ynnTefHAAw+YoKAgs3btWre/j2PHjrnGXCznxsWIeu09/5dqsw5v/N/kC/XaGN+o2b5Qr2uzDm88L2qzjnLedG5cbDW7UQRvY4yZNWuWiYyMNAEBASYuLs7ta+ZHjRplBgwY4DZ+7dq1JjY21gQEBJj27dub1157rcIx3333XRMVFWX8/f1NdHS02wlkFU/WMWDAACOpQhs1apRrzIQJE0xERIQJCAgwrVu3NklJSWbjxo1es4YpU6aYjh07GofDYS6//HJz1VVXmY8++qjCMb39vjDGmEOHDplmzZqZOXPmVHq8C31flP+8RVV/HxfLeeHpOrzxvPB0Dd56XtTmb8rbzovK5i/JzJ8/3zXmYjk3LlbUa+/4v1SbdXjr/6aLvV4b4xs12xfqdW3W4a3nBTX7wp8btl8mDQAAAAAALODzn/EGAAAAAKAhEbwBAAAAALAQwRsAAAAAAAsRvAEAAAAAsBDBGwAAAAAACxG8AQAAAACwEMEbAAAAAAALEbwBAAAAALAQwRsAAAAAAAsRvAEAAAAAsBDBGwAAAAAACxG8AQAAAACw0P8HREXVr4nK5gAAAAAASUVORK5CYII="
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 14
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": "",
   "id": "694c12f1a25cd5b0"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:33:17.941404Z",
     "start_time": "2025-03-26T04:33:17.919407Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from shapely.geometry import Polygon\n",
    "import triangle as tr\n",
    "\n",
    "def plot_polygon(polygon, facecolor='blue', edgecolor='black'):\n",
    "    \"\"\"绘制多边形\"\"\"\n",
    "    plt.fill(*polygon.exterior.xy, facecolor=facecolor, edgecolor=edgecolor)\n",
    "    for interior in polygon.interiors:\n",
    "        plt.fill(*interior.xy, facecolor='white', edgecolor=edgecolor)\n",
    "\n",
    "def polygon_to_triangles(polygon):\n",
    "    \"\"\"将多边形分割为三角形\"\"\"\n",
    "    # 提取顶点坐标（去掉最后一个重复点）\n",
    "    vertices = np.array(polygon.exterior.coords[:-1])\n",
    "    \n",
    "    # 创建线段连接信息\n",
    "    segments = np.array([[i, (i+1)%len(vertices)] for i in range(len(vertices))])\n",
    "    \n",
    "    # 准备三角剖分输入数据\n",
    "    A = {\n",
    "        'vertices': vertices,\n",
    "        'segments': segments,\n",
    "        'holes': None  # 如果没有孔洞可以省略\n",
    "    }\n",
    "    \n",
    "    # 进行约束Delaunay三角剖分\n",
    "    B = tr.triangulate(A, 'p')\n",
    "    \n",
    "    # 检查结果是否包含三角形\n",
    "    if 'triangles' not in B:\n",
    "        raise ValueError(\"三角剖分失败，请检查输入多边形是否有效\")\n",
    "    \n",
    "    # 创建三角形多边形列表\n",
    "    triangles = []\n",
    "    for triangle in B['triangles']:\n",
    "        tri_vertices = B['vertices'][triangle]\n",
    "        triangles.append(Polygon(tri_vertices))\n",
    "    \n",
    "    return triangles\n",
    "\n",
    "# 创建一个凹多边形（L形）\n",
    "polygon = Polygon([\n",
    "    (0, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)\n",
    "])\n",
    "\n",
    "try:\n",
    "    # 分割多边形\n",
    "    convex_parts = polygon_to_triangles(polygon)\n",
    "    \n",
    "    # 绘制结果\n",
    "    plt.figure(figsize=(10, 5))\n",
    "    \n",
    "    # 原始多边形\n",
    "    plt.subplot(1, 2, 1)\n",
    "    plot_polygon(polygon)\n",
    "    plt.title('Original Polygon')\n",
    "    \n",
    "    # 分割后的凸多边形\n",
    "    plt.subplot(1, 2, 2)\n",
    "    colors = plt.cm.tab10.colors\n",
    "    for i, part in enumerate(convex_parts):\n",
    "        plot_polygon(part, facecolor=colors[i % len(colors)])\n",
    "    plt.title('Triangulation Result')\n",
    "    \n",
    "    plt.tight_layout()\n",
    "    plt.show()\n",
    "\n",
    "except Exception as e:\n",
    "    print(f\"错误发生: {str(e)}\")"
   ],
   "id": "f3f3e3580d0f8719",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "错误发生: \n"
     ]
    }
   ],
   "execution_count": 3
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:35:39.908438Z",
     "start_time": "2025-03-26T04:35:39.863438Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from qgis.core import QgsGeometry, QgsFeature\n",
    "\n",
    "# 创建原始多边形\n",
    "original_geom = QgsGeometry.fromWkt('POLYGON((0 0, 2 0, 2 2, 0 2, 0 0))')\n",
    "\n",
    "# 创建分割线\n",
    "split_line = QgsGeometry.fromWkt('LINESTRING(1 0, 1 2)')\n",
    "\n",
    "# 执行分割\n",
    "result, new_geoms, test = original_geom.splitGeometry(split_line.asPolyline(), True)\n",
    "\n",
    "# 输出结果\n",
    "for geom in new_geoms:\n",
    "    print(geom.asWkt())"
   ],
   "id": "f84a9bd54ab2be98",
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'qgis'",
     "output_type": "error",
     "traceback": [
      "\u001B[1;31m---------------------------------------------------------------------------\u001B[0m",
      "\u001B[1;31mModuleNotFoundError\u001B[0m                       Traceback (most recent call last)",
      "Cell \u001B[1;32mIn[6], line 1\u001B[0m\n\u001B[1;32m----> 1\u001B[0m \u001B[38;5;28;01mfrom\u001B[39;00m \u001B[38;5;21;01mqgis\u001B[39;00m\u001B[38;5;21;01m.\u001B[39;00m\u001B[38;5;21;01mcore\u001B[39;00m \u001B[38;5;28;01mimport\u001B[39;00m QgsGeometry, QgsFeature\n\u001B[0;32m      3\u001B[0m \u001B[38;5;66;03m# 创建原始多边形\u001B[39;00m\n\u001B[0;32m      4\u001B[0m original_geom \u001B[38;5;241m=\u001B[39m QgsGeometry\u001B[38;5;241m.\u001B[39mfromWkt(\u001B[38;5;124m'\u001B[39m\u001B[38;5;124mPOLYGON((0 0, 2 0, 2 2, 0 2, 0 0))\u001B[39m\u001B[38;5;124m'\u001B[39m)\n",
      "\u001B[1;31mModuleNotFoundError\u001B[0m: No module named 'qgis'"
     ]
    }
   ],
   "execution_count": 6
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:40:15.886041Z",
     "start_time": "2025-03-26T04:40:15.876040Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from shapely.geometry import Polygon, LineString\n",
    "from shapely.ops import split\n",
    "\n",
    "# 原始多边形\n",
    "original_polygon = Polygon([(0, 0), (2, 0), (2, 2), (0, 2)])\n",
    "\n",
    "# 定义分割线\n",
    "split_line = LineString([(1, 0), (1, 2)])\n",
    "\n",
    "# 执行分割\n",
    "result = split(original_polygon, split_line)\n",
    "\n",
    "# 输出结果 - 正确处理GeometryCollection\n",
    "if result.geom_type == 'GeometryCollection':\n",
    "    # 遍历集合中的所有几何体\n",
    "    for geom in result.geoms:\n",
    "        if geom.geom_type == 'Polygon':  # 确保我们只处理多边形\n",
    "            print(list(geom.exterior.coords))\n",
    "else:\n",
    "    # 如果结果不是GeometryCollection，直接处理\n",
    "    print(list(result.exterior.coords))"
   ],
   "id": "46fbe8a148fac11",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1.0, 0.0), (0.0, 0.0), (0.0, 2.0), (1.0, 2.0), (1.0, 0.0)]\n",
      "[(1.0, 2.0), (2.0, 2.0), (2.0, 0.0), (1.0, 0.0), (1.0, 2.0)]\n"
     ]
    }
   ],
   "execution_count": 8
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-26T04:40:50.104008Z",
     "start_time": "2025-03-26T04:40:50.073011Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from shapely.geometry import Polygon, LineString\n",
    "from shapely.ops import split\n",
    "\n",
    "def split_and_print(polygon, split_line):\n",
    "    result = split(polygon, split_line)\n",
    "    \n",
    "    if result.is_empty:\n",
    "        print(\"分割没有产生任何结果\")\n",
    "        return\n",
    "    \n",
    "    if result.geom_type == 'GeometryCollection':\n",
    "        print(f\"分割产生了 {len(result.geoms)} 个几何体:\")\n",
    "        for i, geom in enumerate(result.geoms, 1):\n",
    "            print(f\"{i}. 类型: {geom.geom_type}\")\n",
    "            if geom.geom_type == 'Polygon':\n",
    "                print(\"   坐标:\", list(geom.exterior.coords))\n",
    "    else:\n",
    "        print(\"分割产生了单个几何体:\", result.geom_type)\n",
    "        if result.geom_type == 'Polygon':\n",
    "            print(\"坐标:\", list(result.exterior.coords))\n",
    "\n",
    "# 测试用例1：简单垂直分割\n",
    "polygon1 = Polygon([(0, 0), (2, 0), (2, 2), (0, 2)])\n",
    "line1 = LineString([(1, 0), (1, 2)])\n",
    "split_and_print(polygon1, line1)\n",
    "\n",
    "# 测试用例2：对角线分割\n",
    "line2 = LineString([(0, 0), (2, 2)])\n",
    "split_and_print(polygon1, line2)"
   ],
   "id": "8cf38a23d52b12ee",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "分割产生了 2 个几何体:\n",
      "1. 类型: Polygon\n",
      "   坐标: [(1.0, 0.0), (0.0, 0.0), (0.0, 2.0), (1.0, 2.0), (1.0, 0.0)]\n",
      "2. 类型: Polygon\n",
      "   坐标: [(1.0, 2.0), (2.0, 2.0), (2.0, 0.0), (1.0, 0.0), (1.0, 2.0)]\n",
      "分割产生了 2 个几何体:\n",
      "1. 类型: Polygon\n",
      "   坐标: [(2.0, 2.0), (2.0, 0.0), (0.0, 0.0), (2.0, 2.0)]\n",
      "2. 类型: Polygon\n",
      "   坐标: [(0.0, 0.0), (0.0, 2.0), (2.0, 2.0), (0.0, 0.0)]\n"
     ]
    }
   ],
   "execution_count": 10
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": "",
   "id": "7e96576edef4d133"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
